package com.wp.动态规划;

/**
 * @author 王萍
 * @date 2018/4/6 0006
 */
public class 最长递增子序列 {
    public static int len = 0;
    public static int[] result;

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6};
        result = new int[arr.length];
        lengthOfLIS(arr);
        System.out.println(len);
    }

    public static void lengthOfLIS(int[] nums) {
//        for (int i = 0; i < nums.length - 1; i++) {
//            dfs(i, nums, 1);
//        }
        dfs(0, nums, 1);
    }

    private static void dfs(int index, int[] nums, int count) {
        if (count > len)
            len = count;
        if (index == nums.length - 1) {
            return;
        }
        for (int i = index + 1; i < nums.length; i++) {
            int c = count;
            if (nums[i] > nums[index]) {
                dfs(i, nums, ++c);
            }
        }
    }
}
